1. Field of the Invention
The present invention concerns a method for sharing the switching bandwidth available for transferring cells of unicast and multicast flows in an asynchronous switching node.
2. Description of the Related Art
As shown in FIG. 1, such a switching node 1 includes a plurality (n1) of input terminal modules or input modules, ITM1, . . . , ITMi, . . . , ITMn1, which are interconnected with a plurality of n2 output terminal modules, or output modules, OTM1, . . . , OTMj, . . . , OTMn2, via an asynchronous switching network 2, according to a conventional arrangement. This type of separate representation of n1 input modules and n2 output modules can reflect either an implementation in which the input and output modules are physically separated, or a logical separation of two types of functions, input and output, implemented in mixed terminal modules combining these two types of functions, in which case the numbers n1 and n2 of modules are generally equal.
This switching node is used to transfer a data block received in an input module of any rank i, ITMi, to at least one output module of any rank j, OTMj, via its switching network 2 according to an internal routing mode of whatever type, for example the type without connection or with connection. A block of external data received on an incoming port of an input module can be switched to leave on an outgoing port of a given output module; in this case such a data block is referred to as a “unicast” data block; it can also be switched by the network 2 to leave on outgoing ports of a plurality of different output modules; in that case such a data block is referred to as “multicast”.
According to known techniques, the external data blocks which are received in the form of variable length packets are converted into cells of internal format in the input modules, typically by packet segmentation. Once transferred to the recipient output modules via the switching network, the cells of internal format are converted back into external data blocks, cells or packets, typically by cell reassembly in the case of external data blocks to be transmitted in the form of variable length packets. Within the switching node, regardless of the type of external data blocks, the asynchronous switching network in question then switches cells of internal format, each cell being transferred from an incoming module to at least one recipient output module. Hereafter, only these cells of internal format are considered, in so far as the problem of the invention concerns the internal transfer of these cells in the switching node and not the external data blocks.
In the input modules of this node, two types of cells to be transferred via the cell switching network 2 are considered: a first type of cell called unicast, UC, which must be routed to a single given recipient output module, and a second type of cell called multicast, MC, which must be routed to a plurality of N given recipient output modules among the n2 output modules of the node (where 1<N≦n2).
In the case of multicast cells, to perform the required transformation of such a cell into N cells to be delivered to each of N recipient output modules, two conventional methods are known:                the first method consists in generating N copies of a multicast cell in the input module, in such a way that the latter transmits to the switching network N unicast cells, each intended for one of the N recipient output modules required for this multicast cell;        the second method consists in transmitting to the switching network, from the input module, a single copy of the multicast cell MC, the switching network then itself able to generate, according to a known technique, the N copied cells UCa, . . . , UCn from one multicast cell while routing each of these N copied cells to deliver them to each of the N recipient output modules required for this multicast cell.        
The invention concerns this second method.
FIG. 2 illustrates outgoing flows of cells delivered to a given output module OTMd, coming from various input modules ITM1, . . . , ITMn1 in the switching node 1. The flows of cells transferred via the switching network run the risk of creating congestion in this network each time the overall rate of the traffic of cells delivered to an output module, such as OTMd, becomes excessive in respect of the bandwidth allowed to access this output module, in so far as the capacity for transferring cells via the switching network is physically limited by characteristics specific to this network.
To avoid such a congestion situation in the switching network, the conventional provision is to regulate, in each input module, the transfer rates of cells to each output module of the node, in such a way that the overall rate of traffic of cells delivered to each output module is not excessive.
To this end, according to a known technique, each input module, as illustrated in FIG. 3, is equipped with buffer stores 3 for temporarily storing cells, and these buffer stores are structured as a plurality of queues Q1, . . . , Qj, . . . , Qn2 which are managed respectively for each outgoing cell flow corresponding to the subset of cells delivered, by the switching network, to a given output module.
According to this technique used in such an input module ITMi, after processing by known functions of the input interface and for converting into internal cells (not represented in FIG. 3), the cells are distributed to the various queues, such as Q1, . . . , Qj, . . . , Qn2, according to their recipient output module OTM1, . . . , OTMj, . . . , OTMn2. To output a cell from a queue and transmit it to the switching network, a queue multi-server 4 uses one if its service cycles to read the corresponding data in the queue and extract the data from it. Such a queue multi-server distributes its service cycles to the various queues, proportionally to the cell service rate GOCRj attributed to each queue Qj to transfer cells intended for the corresponding output module OTMj. Operation of all the queues of an input module is controlled by a queue management unit 5, in this case assumed to be assigned to this input module, as illustrated schematically in FIG. 3. This queue management unit controls the departure of cells stored in the buffer stores to the switching network at service times according to a cell service rate attributed to each of the cell flows.
The composition of the output modules of the node 1 is not detailed here in so far as each output module can be implemented in the conventional way, with a plurality of registers or stores for receiving data blocks, converting them into internal cells and then transmitting these cells to the output interface functions of this input module. The composition of buffer memories, the queue multiserver or the queue management unit is also not detailed and can involve hardware means (in particular processors and memories), and software means that are appropriate and known per se.
FIG. 4 is a flowchart of the steps implemented for the sharing of the bandwidth available for unicast flows in the switching node of FIGS. 1 to 3. FIG. 4 taken as a whole is representative of a mechanism for controlling flows inside the switching node; such a flow control mechanism is described in an article entitled “Buffering and Flow Control for Statistical Multiplexing in an ATM Switch” by T. WORSTER & al, which was published in April 1995 in volume No. 1 pages 273-277 of the report of the International Switching Symposium ISS 95.
According to the method described, to dynamically achieve a sharing of the overall switching bandwidth available at a node, the following is required:                an evaluation of the volume of queuing traffic stored temporarily in input queues which each input module includes, for each of the output modules likely to be recipients in relation to it;        a determination, according to the volume of queuing traffic observed, of a parameter called bandwidth request, for each pair made up of a given input module and a given recipient output module;        a collection of these bandwidth request parameters concerning each recipient output module, at the various input modules;        for each output module, sharing of the switching bandwidth available toward this recipient output module, according to these various bandwidth request parameters relating to the various input modules;        delivery to each input module of a bandwidth allocation parameter, for each of the pairs of modules that it forms with the various output modules of the node.        
By implementing such a method at the level of an internal flow control mechanism of an asynchronous switching node, the available switching bandwidth can be shared, based on the bandwidth request parameter values determined according to the volume of queuing traffic observed at the queues of the input modules of the node.
Such a flow control mechanism is based on the use, from the point of view of traffic, of a virtual ingress/egress pipe concept, VIEPi/j, for each pair (ITMi, OTMj) of an input module ITMi and an output module OTMj.
In the left part of FIG. 4, the steps implemented at input module level are shown, and in the right part of the figure, the available bandwidth sharing step implemented at output module level, or in a more centralized manner, is represented.
The first step 10, implemented by the flow control mechanism in each input module ITMi, is a step for preparing a bandwidth request parameter BRi/j, for each pair (ITMi, OTMj) made up of this input module ITMi and an output module OTMj. For each given pair (ITMi, OTMj), this step consists in accumulating the various individual bandwidth requests U-BR[i/j]p of each of the different unicast flows UF[i/j]p present in the input module ITMi and intended for the output module OTMj of this module pair.
For each unicast flow UF[i/j]p present in the input module ITMi, the individual bandwidth request parameter U-BR[i/j]p can for example have a value which is determined according to the number of cells belonging to flows that are stored in the buffer memories of the input module. Other forms of bandwidth request can also be used, for example that for which the value is determined according to the relative weight of priority associated with each of the flows, as described in French patent application No 01 12446 filed on Sep. 27, 2001.
This first step 10 thus provides, for all the module pairs (ITMi, OTMj), bandwidth request parameters BRi/j per module pair. These parameters are provided as the input to the second step 14 in FIG. 4, as symbolized in the figure by the arrow 12.
The second step 14, implemented by the flow control mechanism for each given output module OTMj, is a step for sharing, according to the bandwidth request parameters BRi/j per module pair that were established during the first step, the bandwidth available for accessing this given output module, that is to say for the cell traffic of all unicast flows concerning the various module pairs (ITMi/OTMj) having this same given output module OTMj as recipient. This sharing step is relative to each output module, but it can also be performed physically at each output module, or at a more centralized level. This second step provides, for each of the virtual ingress/egress pipes VIEPi/j, a bandwidth allocation parameter BGi/j per module pair. For the module pairs (ITMi, OTMj) corresponding to this virtual pipe, this bandwidth allocation parameter per pair can be used to regulate the transfer of cells from all unicast flows associated with this module pair, that is to say coming from the input module ITMi and intended for the output module OTMj.
The third step symbolized in FIG. 4 by the arrow 16 is a step for supplying, to each of the input modules ITMi, various bandwidth allocation parameters BGi/j related to the module pairs (ITMi/OTMj) having this input module as source. At the end of this third step, an input module ITMi therefore has parameters BGi/j for allocating bandwidth toward each output module OTMj for which the input module had delivered, during the first step, a bandwidth request parameter BRi/j for the corresponding module pair (ITMi, OTMj). A bandwidth allocation parameter BGi/j between an input module ITMi and an output module OTMj corresponds, in terms of traffic, to the conceptual modeling of a virtual ingress/egress type VIEPi/j between the input module ITMi and the output module OTMj.
The fourth step, symbolized by the reference 18 in FIG. 4, is a step for distributing the bandwidth allocated per module pair, which step is performed at the level of each input module ITMi. From each of these parameters of bandwidth allocation BGi/j per module pair (ITMi, OTMj), this allocated bandwidth is distributed by determining the individual bandwidth allocation U-BG[i/j]p for each of the unicast flows UF[i/j]p associated with this module pair (ITMi, OTMj). This individual allocated bandwidth U-BG[i/j]p forms the cell service rate SSR[i/j]p attributed to each of these flows.
FIG. 4 shows also by the arrow 20, the provision of various cell service rates SSR[i/j]p attributed to each of the flows. These different cell service rates are delivered to the queue management unit 5 of FIG. 3, to control the respective order of cells from different flows in the queues 3, as symbolized by the reference 22 in FIG. 4. The dash-dotted line in FIG. 4, between the distribution step referenced 18 and the queue management step 22, indicates that this queue management step 22 is not part of the flow control mechanism.
The flow control mechanism of FIG. 4 is designed to regulate the traffic of flows of unicast cells, which are well suited to processing by module pair (ITMi, OTMj) according to virtual ingress/egress type concept VIEPi/j. However it does not apply to flows of multicast cells, given their plurality of recipient output modules which is not compatible with the concept of virtual ingress/egress pipe per module pair. There is therefore a need for a method for sharing the switching bandwidth available for transferring cells of unicast and multicast flows in an asynchronous switching node.